﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DiscreteMath
{
    static class RpnConverter<T> where T : ILanguageOperator<T>
    {
        public struct Operator
        {
            public int Precedence;
            public bool IsUnary;
            public OperatorAssociativity Associativity;
            public Func<T, T, T> Evaluate;

            public enum OperatorAssociativity { Right, Left, None }
        }

        public static Dictionary<char, Operator> OperatorTokens = new Dictionary<char, Operator>() 
                { 
                    { 
                        SpecialSigns.UnionSign, new Operator() 
                            { Precedence = 0, Evaluate = (first, second) => first.Union(second) } 
                    }, 
                    { 
                        SpecialSigns.ConcatenationSign, new Operator() 
                            { Precedence = 1, Evaluate = (first, second) => first.Concatenate(second) } 
                    },
                    { 
                        SpecialSigns.KleeneeStarSign, new Operator() 
                        { 
                            Precedence = 2, Associativity = Operator.OperatorAssociativity.Left, IsUnary = true,
                            Evaluate = (first, second) => first.KleneeStar() 
                        }
                    },
                };


        public static T EvaluateRegex(string expression, Func<char, ISet<char>, T> deviceFromLetterGenerator)
        {
            string rpn = ConvertToRPN(expression);
            Stack<T> deviceValues = new Stack<T>();

            ISet<char> alphabet = new HashSet<char>(
                rpn.Where(token => !OperatorTokens.ContainsKey(token)));


            foreach (char token in rpn)
            {
                if (alphabet.Contains(token))
                {
                    T singleLetterAutomaton = deviceFromLetterGenerator(token, alphabet);
                    deviceValues.Push(singleLetterAutomaton);
                }
                else
                {
                    Operator currentOperator = OperatorTokens[token];
                    if (currentOperator.IsUnary)
                    {
                        T topOfStack = deviceValues.Pop();
                        T evaluation = currentOperator.Evaluate(topOfStack, topOfStack);
                        deviceValues.Push(evaluation);
                    }
                    else
                    {
                        T second = deviceValues.Pop();
                        T first = deviceValues.Pop();
                        T result = currentOperator.Evaluate(first, second);
                        deviceValues.Push(result);
                    }
                }
            }

            return deviceValues.Pop();
        }

        public static string ConvertToRPN(string expression)
            {
                Stack<char> operators = new Stack<char>();
                StringBuilder rpnExpression = new StringBuilder();

                char leftBracket = '(',
                    rightBracket = ')';

                Func<char, bool> isLetter =
                    (symbol) => !OperatorTokens.ContainsKey(symbol) && symbol != leftBracket && symbol != rightBracket;
                StringBuilder temp = new StringBuilder();
                for (int i = 0; i < expression.Length - 1; i++)
                {
                    temp.Append(expression[i]);
                    bool shouldConcatenate =
                        (expression[i] == rightBracket ||
                        isLetter(expression[i]) ||
                        expression[i] == SpecialSigns.KleeneeStarSign) &&
                        (isLetter(expression[i + 1]) ||
                        expression[i + 1] == leftBracket);
                    if (shouldConcatenate)
                    {
                        temp.Append(SpecialSigns.ConcatenationSign);
                    }
                }
                temp.Append(expression.Last());

                expression = temp.ToString();
                foreach (char token in expression)
                {
                    if (!OperatorTokens.ContainsKey(token) && token != leftBracket && token != rightBracket)
                    {
                        rpnExpression.Append(token);
                    }
                    else if (OperatorTokens.ContainsKey(token))
                    {
                        while
                            (operators.Count != 0 &&
                            OperatorTokens.ContainsKey(operators.Peek()) &&
                            (OperatorTokens[token].Precedence < OperatorTokens[operators.Peek()].Precedence ||
                            (OperatorTokens[token].Associativity == Operator.OperatorAssociativity.Left &&
                            (OperatorTokens[token].Precedence <= OperatorTokens[operators.Peek()].Precedence))))
                        {
                            rpnExpression.Append(operators.Pop());
                        }
                        operators.Push(token);
                    }
                    else if (token == leftBracket)
                    {
                        operators.Push(token);
                    }
                    else if (token == rightBracket)
                    {
                        try
                        {
                            while (operators.Peek() != leftBracket)
                            {
                                rpnExpression.Append(operators.Pop());
                            }
                        }
                        catch (InvalidOperationException)
                        {
                            throw new InvalidOperationException("Mismatched parentheses in expression!");
                        }
                        operators.Pop();
                    }
                }
                while (operators.Count != 0)
                {
                    char next = operators.Pop();
                    if (next == leftBracket || next == rightBracket)
                    {
                        throw new InvalidOperationException("Mismatched parentheses in expression!");
                    }
                    rpnExpression.Append(next);
                }
                return rpnExpression.ToString();
            }

    }
}
